//
// Created by fengg on 2020/5/18.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define NO_ERROR                    0
#define NOT_FOUND_ERROR             1
#define ALREADY_EXIST_ERROR         1

#define RIGHT_CHILD                 0
#define LEFT_CHILD                  1

typedef struct _bin_tree {
    int data;
    struct _bin_tree *left_child;
    struct _bin_tree *right_child;
    struct _bin_tree *parent;
} BinTree,*LPBinTree;

///
/// \param flag
/// \param lpBinTree
/// \param data
/// \return
int AppendTo(int flag,LPBinTree lpBinTree,int data){
    LPBinTree lpNewTree = malloc(sizeof(BinTree));
    memset(lpNewTree,0, sizeof(BinTree));
    lpNewTree->data = data;
    if (flag == LEFT_CHILD)
        lpBinTree->left_child = lpNewTree;
    else
        lpBinTree->right_child = lpNewTree;
    lpNewTree->parent = lpBinTree;
    return NO_ERROR;
}

/// 将data插入以lpTreeNode为root的排序树中
/// \param lpTreeNode 待插入的树root结点
/// \param data       待插入值
/// \return
/// 返回值如下
/// NO_ERROR 0 插入成功
/// ALREADY_EXIST_ERROR 1 插入失败,已经存在data这个值
int NodeInsert(LPBinTree lpTreeNode,int data){

    if(data < lpTreeNode->data){
        if(lpTreeNode->left_child)
            return NodeInsert(lpTreeNode->left_child,data);
        else
            return AppendTo(LEFT_CHILD,lpTreeNode,data);

    } else if(data > lpTreeNode->data) {
        if(lpTreeNode->right_child)
            return NodeInsert(lpTreeNode->right_child,data);
        else
            return AppendTo(RIGHT_CHILD,lpTreeNode,data);

    } else {
        return ALREADY_EXIST_ERROR;
    }
}

/// 插入树
/// \param lpTree
/// \param data
/// \return
int InsertTree(LPBinTree *lpTree,int data){
    if(!*lpTree) {
        *lpTree =  malloc(sizeof(BinTree));
        memset(*lpTree,0, sizeof(BinTree));
        (*lpTree)->data = data;
        return NO_ERROR;
    }
    return NodeInsert(*lpTree,data);
}

/// 树的输出格式
/// \param binTree
void print_tree(LPBinTree binTree){
    printf("%d ",binTree->data);
}

/// 中序遍历
/// \param binTree
void GoM(BinTree *binTree) {
    if(!binTree)
        return;
    GoM(binTree->left_child);
    print_tree(binTree);
    GoM(binTree->right_child);
}
/// 搜索树
/// \param lpTree 待搜索的树
/// \param data   待搜索的值
/// \param lpTarget 如果不为NULL,将会设置为查询成功的值所在结点地址
/// \return
int BinSearch(LPBinTree lpTree , int data , LPBinTree *lpTarget){
    if(!lpTree)
        return NOT_FOUND_ERROR;
    if(lpTree->data == data){
        if(lpTarget)
            *lpTarget = lpTree;
        return NO_ERROR;
    } else if (lpTree->data > data){
        return BinSearch(lpTree->left_child,data , lpTarget);
    } else {
        return BinSearch(lpTree->right_child,data , lpTarget);
    }
}
/// 寻找结点lpBinTree的中序遍历的下一结点
/// \param lpBinTree 待查找结点
/// \return 无下一结点返回NULL,有则将其指针返回
LPBinTree FindNextMid(LPBinTree lpBinTree){
    if (lpBinTree)
        lpBinTree = lpBinTree->right_child;
    if (lpBinTree)
        while (lpBinTree->left_child)
            lpBinTree = lpBinTree->left_child;
    return lpBinTree;
}

/// 删除指定值的结点
/// \param lpBinTree 待从中删除的树的root
/// \param data 指定的值
/// \return
int BinRemove(LPBinTree lpBinTree , int data){
    int Err;
    LPBinTree lpTarget;
    LPBinTree lpReplace;
    if(!lpBinTree)
        return NOT_FOUND_ERROR;
    Err = BinSearch(lpBinTree,data,&lpTarget);
    if(Err == NOT_FOUND_ERROR)
        return NOT_FOUND_ERROR;
    lpReplace = FindNextMid(lpTarget);
    if (lpReplace){
        lpTarget->data = lpReplace->data;
        if (lpReplace->parent != lpTarget){
            lpReplace->parent->left_child = lpReplace->right_child;
        } else {
            lpTarget->right_child = lpReplace->right_child;
        }
        free(lpReplace);
    } else {
        if(lpTarget->parent){
            if(lpTarget->parent->right_child == lpTarget){
                lpTarget->parent->right_child = lpTarget->left_child;
            } else {
                lpTarget->parent->left_child = lpTarget->left_child;
            }
        } else {
            LPBinTree lpTemp = lpTarget->left_child;
            lpTarget->data = lpTemp->data;
            lpTarget->left_child = lpTemp->left_child;
            free(lpTemp);
        }
    }
    return NO_ERROR;

}

//tibble
// data.frame
// 工作空间和变量赋值
//browser

/// 垃圾回收
/// \param lpBinTree
void TreeGc(LPBinTree lpBinTree){
    if(!lpBinTree)
        return;
    TreeGc(lpBinTree->left_child);
    TreeGc(lpBinTree->right_child);
    free(lpBinTree);
}

/// 读取有效的数值,当数据无效会不断重试
/// \param lpNumber
void ReadValidNumber(int *lpNumber){
    char string[16] = {0};
    char *lpEnd;
    while (1){
        scanf("%s",string);
        *lpNumber = strtol(string,&lpEnd,10);
        if(!*lpEnd)
            break;
        else
            printf("ERROR: In \"%s\",\"%s\" is invalid\nTry Again\n",string,lpEnd);
    }
}

int main() {
    int data;
    int Err;
    LPBinTree lpBinTree = NULL;

    ///建立树
    ReadValidNumber(&data);
    while(data){
        Err = InsertTree(&lpBinTree,data);
        if(Err == ALREADY_EXIST_ERROR){
            puts("already exist \n");
        }
        ReadValidNumber(&data);
    }
    GoM(lpBinTree); putchar('\n');

    ///查询值
    ReadValidNumber(&data);
    Err = BinSearch(lpBinTree,data,NULL);
    if (!Err) {
        printf("The node(%d) Search Succeed.\n",data);
    } else {
        printf("The node(%d) not exist.\n",data);
    }

    ///插入值
    ReadValidNumber(&data);
    Err = NodeInsert(lpBinTree,data);
    if (Err == ALREADY_EXIST_ERROR){
        printf("The node(%d) already exist.\n",data);
    }
    GoM(lpBinTree);  putchar('\n');

    ///移除值
    ReadValidNumber(&data);
    Err = BinRemove(lpBinTree,data);
    if(Err == NOT_FOUND_ERROR){
        printf("The node(%d) not exist.\n",data);
    }
    GoM(lpBinTree);


    TreeGc(lpBinTree);
    return NO_ERROR;
}